ff1588d761d55f48f61a52249e1dcc24

<!DOCTYPE html>

<title>Jacobi-Symbol</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Jacobi-Symbol</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Das Jacobi-Symbol, benannt nach <a href="Carl_Gustav_Jacob_Jacobi" title="Carl Gustav Jacob Jacobi">Carl Gustav Jacob Jacobi</a>, ist eine Verallgemeinerung des <a href="Legendre-Symbol" title="Legendre-Symbol">Legendre-Symbols</a>. Das Jacobi-Symbol kann wiederum zum <a href="Kronecker-Symbol" title="Kronecker-Symbol">Kronecker-Symbol</a> verallgemeinert werden. Die Notation ist die gleiche wie die des Legendre-Symbols:

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{n}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/42ee8ba7e649c05c1a3642c7a932095c47e25353.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:5.006ex; height:4.843ex;" alt="{\displaystyle \left({\frac {a}{n}}\right)}" loading="lazy"> oder auch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a/n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a/n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5380e7fa8cd49a34aa0cc7c2c5d4e3479724b6ef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.596ex; height:2.843ex;" alt="{\displaystyle (a/n)}" loading="lazy"></dd></dl>

Um zwischen dem Legendre-Symbol und dem Jacobi-Symbol zu unterscheiden, schreibt man auch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(a,p)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(a,p)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c07813499283d234a6b7ede8ecacba160e3cbdf2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.825ex; height:2.843ex;" alt="{\displaystyle L(a,p)}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J(a,n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J(a,n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a02484cb12b6d50ae2aa6eeae9ac40e55abe2cb3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.939ex; height:2.843ex;" alt="{\displaystyle J(a,n)}" loading="lazy">.

Dabei muss <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> im Gegensatz zum Legendre-Symbol keine <a href="Primzahl" title="Primzahl">Primzahl</a> sein, allerdings muss es eine ungerade <a href="Nat%C3%BCrliche_Zahl" title="Natürliche Zahl">natürliche Zahl</a> sein. Für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> sind beim Jacobi-Symbol wie beim Legendre-Symbol alle ganzen Zahlen zugelassen.

<div class="mw-heading mw-heading2"><h2 id="n_ist_eine_Primzahl">n ist eine Primzahl</h2></div>

Falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> eine Primzahl ist, ist das Jacobi-Symbol nach Definition gleich dem Legendre-Symbol:

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mstyle>

</mrow>

<mtext> ein quadratischer Rest modulo </mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mstyle>

</mrow>

<mtext> ein quadratischer Nichtrest modulo </mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mstyle>

</mrow>

<mtext> ein Teiler von </mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

<mtext> kongruent </mtext>

</mstyle>

</mrow>

<mtext> modulo </mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{n}}\right)={\begin{cases}1&{\mbox{wenn }}a{\mbox{ ein quadratischer Rest modulo }}n{\mbox{ ist}}\\-1&{\mbox{wenn }}a{\mbox{ ein quadratischer Nichtrest modulo }}n{\mbox{ ist}}\\0&{\mbox{wenn }}n{\mbox{ ein Teiler von }}a{\mbox{ ist (also }}a{\mbox{ kongruent }}0{\mbox{ modulo }}n{\mbox{)}}\end{cases}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7de046ed7e891e308250db58af6585be62d72154.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:73.429ex; height:8.509ex;" alt="{\displaystyle \left({\frac {a}{n}}\right)={\begin{cases}1&{\mbox{wenn }}a{\mbox{ ein quadratischer Rest modulo }}n{\mbox{ ist}}\\-1&{\mbox{wenn }}a{\mbox{ ein quadratischer Nichtrest modulo }}n{\mbox{ ist}}\\0&{\mbox{wenn }}n{\mbox{ ein Teiler von }}a{\mbox{ ist (also }}a{\mbox{ kongruent }}0{\mbox{ modulo }}n{\mbox{)}}\end{cases}}}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="n_ist_keine_Primzahl">n ist keine Primzahl</h2></div>

Ist die <a href="Primfaktorzerlegung" title="Primfaktorzerlegung">Primfaktorzerlegung</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=p_{1}^{\nu _{1}}\cdot p_{2}^{\nu _{2}}\cdots p_{k}^{\nu _{k}}}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=p_{1}^{\nu _{1}}\cdot p_{2}^{\nu _{2}}\cdots p_{k}^{\nu _{k}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/111479d7dcf74393300ce7dfc55d0d0ca45045a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:18.834ex; height:3.176ex;" alt="{\displaystyle n=p_{1}^{\nu _{1}}\cdot p_{2}^{\nu _{2}}\cdots p_{k}^{\nu _{k}}}" loading="lazy">, so definiert man

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{\nu _{1}}\cdots \left({\frac {a}{p_{k}}}\right)^{\nu _{k}}.}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec8d5789061fa8519d6544a2221ed6c8ded7c539.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:29.025ex; height:6.176ex;" alt="{\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{\nu _{1}}\cdots \left({\frac {a}{p_{k}}}\right)^{\nu _{k}}.}" loading="lazy"></dd></dl>

Für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d9ec7e1edc2e6d98f5aec2a39ae5f1c99d1e1425.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n=1}" loading="lazy"> wird üblicherweise <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {a}{1}}\right)=1}">

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{1}}\right)=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec3320defb0a4296e24b4b3b69266b3e3b5128ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:9.102ex; height:4.843ex;" alt="{\displaystyle \left({\frac {a}{1}}\right)=1}" loading="lazy"> gesetzt (leeres Produkt).

Beispiel:

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {11}{91}}\right)=\left({\frac {11}{7}}\right)\cdot \left({\frac {11}{13}}\right)=\left({\frac {4}{7}}\right)\cdot \left({\frac {11}{13}}\right)=1\cdot (-1)=-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/075b3f0b4556fb43ef2e8c6a4b2af05f7e8967e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:58.093ex; height:6.176ex;" alt="{\displaystyle \left({\frac {11}{91}}\right)=\left({\frac {11}{7}}\right)\cdot \left({\frac {11}{13}}\right)=\left({\frac {4}{7}}\right)\cdot \left({\frac {11}{13}}\right)=1\cdot (-1)=-1}" loading="lazy"></dd></dl>

Achtung: Falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> keine Primzahl ist, gibt das Jacobi-Symbol nicht an, ob <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> ein <a href="Quadratischer_Rest" title="Quadratischer Rest">quadratischer Rest</a> modulo <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> ist (wie beim Legendre-Symbol). Eine notwendige Bedingung dafür, dass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> ein quadratischer Rest modulo <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> ist, ist allerdings, dass das Jacobi-Symbol ungleich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/704fb0427140d054dd267925495e78164fee9aac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:2.971ex; height:2.343ex;" alt="{\displaystyle -1}" loading="lazy"> ist. Beispielsweise erhält man für vier verschiedene Reste a modulo 15 für

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{15}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/71f4832232dad659ee86fc53a62f5dcef37148ff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:5.937ex; height:4.843ex;" alt="{\displaystyle \left({\frac {a}{15}}\right)}" loading="lazy"></dd></dl>

den Wert 1, jedoch sind nur zwei davon Quadrate modulo 15 (man erhält für 1, 2, 4, 8 den Wert 1, Quadrate sind nur 1 und 4). Den Wert 0 erhält man siebenmal (0, 3, 5, 6, 9, 10, 12), davon sind aber auch nur vier Quadrate (0, 6, 9, 10). Übrig bleiben die vier Werte, für die man -1 erhält (7, 11, 13, 14), hier erhält man, wie bereits angesprochen, niemals ein Quadrat.

<div class="mw-heading mw-heading2"><h2 id="Allgemeine_Definition">Allgemeine Definition</h2></div>

Allgemein ist das Jacobi-Symbol <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J(a,n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J(a,n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a02484cb12b6d50ae2aa6eeae9ac40e55abe2cb3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.939ex; height:2.843ex;" alt="{\displaystyle J(a,n)}" loading="lazy"> über einen <a href="Charakter_(Mathematik)" title="Charakter (Mathematik)">Charakter</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \chi _{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi _{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bbd6b3dfa2b07ba35c0294c0b22321a9852bb6be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.674ex; height:2.009ex;" alt="{\displaystyle \chi _{n}}" loading="lazy"> der Gruppe <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} /n\mathbb {Z} }">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} /n\mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f2120ebbc85f91df66c6de5446367bf9fd620844.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.658ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} /n\mathbb {Z} }" loading="lazy"> definiert:

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

<mtd>

<mtext>falls ggT</mtext>

</mstyle>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext>sonst</mtext>

</mstyle>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{n}}\right):={\begin{cases}\chi _{n}(a+n\mathbb {Z} )&{\mbox{falls ggT}}(a,n)=1\\0&{\mbox{sonst}}\end{cases}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1c3e6ecdbb73c20afd81bbba269195ea0d87f105.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:43.464ex; height:6.176ex;" alt="{\displaystyle \left({\frac {a}{n}}\right):={\begin{cases}\chi _{n}(a+n\mathbb {Z} )&{\mbox{falls ggT}}(a,n)=1\\0&{\mbox{sonst}}\end{cases}}}" loading="lazy"></dd></dl>

Dabei ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \chi _{n}(a+n\mathbb {Z} )}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi _{n}(a+n\mathbb {Z} )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7439400ce992615cc02230bbc1717bc8bba3211d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.498ex; height:2.843ex;" alt="{\displaystyle \chi _{n}(a+n\mathbb {Z} )}" loading="lazy"> die folgende Funktion:

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi _{n}(a+n\mathbb {Z} ):=\prod _{x\in H}\varepsilon _{x}(a)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/96c23f896e117c188a6bb1963dd828e084b8c45b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:24.421ex; height:5.676ex;" alt="{\displaystyle \chi _{n}(a+n\mathbb {Z} ):=\prod _{x\in H}\varepsilon _{x}(a)}" loading="lazy"></dd></dl>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> ist dabei ein beliebiges <a href="Halbsystem" title="Halbsystem">Halbsystem</a> modulo <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, da der Wert von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \chi _{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi _{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bbd6b3dfa2b07ba35c0294c0b22321a9852bb6be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.674ex; height:2.009ex;" alt="{\displaystyle \chi _{n}}" loading="lazy"> nicht von der Wahl des Halbsystems abhängt. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon _{x}(a)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon _{x}(a)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9a9e9d79ac9549587c0f7216d074d05ec6c2ad70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.295ex; height:2.843ex;" alt="{\displaystyle \varepsilon _{x}(a)}" loading="lazy"> bezeichnet den Korrekturfaktor von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> bezüglich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy">:

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext>falls </mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

<mtext> im gleichen Halbsystem liegen</mtext>

</mstyle>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext>sonst</mtext>

</mstyle>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon _{x}(a):={\begin{cases}1&{\mbox{falls }}x{\mbox{ und }}a\cdot x{\mbox{ im gleichen Halbsystem liegen}}\\-1&{\mbox{sonst}}\end{cases}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e369875d206ddbc40d7bbe31d021ebeec86cd4a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:62.735ex; height:6.176ex;" alt="{\displaystyle \varepsilon _{x}(a):={\begin{cases}1&{\mbox{falls }}x{\mbox{ und }}a\cdot x{\mbox{ im gleichen Halbsystem liegen}}\\-1&{\mbox{sonst}}\end{cases}}}" loading="lazy"></dd></dl>

Eine alternative Definitionsmöglichkeit liefert das <a href="Lemma_von_Zolotareff" title="Lemma von Zolotareff">Lemma von Zolotareff</a>, nach dem das Jacobi-Symbol gleich dem <a href="Vorzeichen_(Permutation)" title="Vorzeichen (Permutation)">Vorzeichen</a> einer speziellen <a href="Permutation" title="Permutation">Permutation</a> ist.

<div class="mw-heading mw-heading2"><h2 id="Geschlossene_Darstellung">Geschlossene Darstellung</h2></div>

Die folgende Formel ist eine geschlossene Darstellung des Werts des Jacobi-Symbols:

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</munderover>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</munderover>

<mrow>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{n}}\right)=\prod _{k=1}^{{\frac {1}{2}}(n-1)}\prod _{h=1}^{{\frac {1}{2}}(a-1)}\operatorname {sgn} \left(\left({\frac {k}{n}}-{\frac {h}{a}}\right)\left({\frac {k}{n}}+{\frac {h}{a}}-{\frac {1}{2}}\right)\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5caadc01d4fb6eb3aece8726a8c6149cf081ff32.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:53.855ex; height:8.676ex;" alt="{\displaystyle \left({\frac {a}{n}}\right)=\prod _{k=1}^{{\frac {1}{2}}(n-1)}\prod _{h=1}^{{\frac {1}{2}}(a-1)}\operatorname {sgn} \left(\left({\frac {k}{n}}-{\frac {h}{a}}\right)\left({\frac {k}{n}}+{\frac {h}{a}}-{\frac {1}{2}}\right)\right)}" loading="lazy"></dd></dl>

Zur effektiven Berechnung ist diese Formel jedoch wenig geeignet, da sie für größere <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a,n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a,n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1d18dddf2c7bb3f21f131947e9f5aa376acd0d81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.658ex; height:2.009ex;" alt="{\displaystyle a,n}" loading="lazy"> schnell sehr viele Faktoren aufweist.

<div class="mw-heading mw-heading2"><h2 id="Effiziente_Berechnung_des_Jacobi-Symbols">Effiziente Berechnung des Jacobi-Symbols</h2></div>

In den meisten Fällen, in denen man die Berechnung des Jacobi-Symbols benötigt, so beim <a href="Solovay-Strassen-Test" title="Solovay-Strassen-Test">Solovay-Strassen-Test</a>, hat man keine Primfaktorzerlegung der Zahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J(a,n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J(a,n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a02484cb12b6d50ae2aa6eeae9ac40e55abe2cb3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.939ex; height:2.843ex;" alt="{\displaystyle J(a,n)}" loading="lazy">, sodass sich das Jacobi-Symbol nicht auf das Legendre-Symbol zurückführen lässt. Zudem ist die oben angegebene geschlossene Darstellung für größere <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a,n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a,n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1d18dddf2c7bb3f21f131947e9f5aa376acd0d81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.658ex; height:2.009ex;" alt="{\displaystyle a,n}" loading="lazy"> nicht effizient genug.

Es gibt jedoch ein paar Rechenregeln, mit denen sich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J(a,n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J(a,n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a02484cb12b6d50ae2aa6eeae9ac40e55abe2cb3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.939ex; height:2.843ex;" alt="{\displaystyle J(a,n)}" loading="lazy"> effizient bestimmen lässt. Diese Regeln ergeben sich unter anderem aus dem <a href="Quadratisches_Reziprozit%C3%A4tsgesetz" title="Quadratisches Reziprozitätsgesetz">quadratischen Reziprozitätsgesetz</a>, das auch für das Jacobi-Symbol seine Gültigkeit besitzt.

Das wichtigste Prinzip ist das folgende: Für alle ungeraden ganzen Zahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m,n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m,n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6568e95b6bf8f39b7fd2c9b52b7b00ee124c6250.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.469ex; height:2.009ex;" alt="{\displaystyle m,n}" loading="lazy"> größer 1 gilt:

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {m}{n}}\right)=(-1)^{{\frac {(m-1)}{2}}{\frac {(n-1)}{2}}}\left({\frac {n}{m}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5b478b67eb9f0be6fc099b77ddd7abe45ac43489.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:28.934ex; height:5.509ex;" alt="{\displaystyle \left({\frac {m}{n}}\right)=(-1)^{{\frac {(m-1)}{2}}{\frac {(n-1)}{2}}}\left({\frac {n}{m}}\right)}" loading="lazy"></dd></dl>

Diese Regel ist das quadratische Reziprozitätsgesetz für das Jacobi-Symbol. Mit ihrer Hilfe, sowie wenigen weiteren Rechenregeln, lässt sich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J(a,b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J(a,b)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cdc043f08d59c42c1641bf1cb272ca28d041839d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.542ex; height:2.843ex;" alt="{\displaystyle J(a,b)}" loading="lazy"> für alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a,b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a,b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/181523deba732fda302fd176275a0739121d3bc8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.261ex; height:2.509ex;" alt="{\displaystyle a,b}" loading="lazy"> mit verhältnismäßig geringem Aufwand bestimmen, der vergleichbar mit dem des <a href="Euklidischer_Algorithmus" title="Euklidischer Algorithmus">euklidischen Algorithmus</a> zur Bestimmung des größten gemeinsamen Teilers ist. Die Rechenregeln, die zusätzlich benötigt werden, sind die folgenden:

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</msup>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {2}{n}}\right)=(-1)^{\frac {n^{2}-1}{8}}={\begin{cases}1,&n\equiv \pm 1{\pmod {8}}\\-1,&n\equiv \pm 3{\pmod {8}}\end{cases}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bcf36bfe3bc4c8cff7a4113b49651986fab7301a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:46.458ex; height:6.343ex;" alt="{\displaystyle \left({\frac {2}{n}}\right)=(-1)^{\frac {n^{2}-1}{8}}={\begin{cases}1,&n\equiv \pm 1{\pmod {8}}\\-1,&n\equiv \pm 3{\pmod {8}}\end{cases}}}" loading="lazy"></li>

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

<msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {-1}{n}}\right)=(-1)^{\frac {n-1}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f48f49e42c6611c68bc1df748ba9a81123ef27e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:18.681ex; height:6.176ex;" alt="{\displaystyle \left({\frac {-1}{n}}\right)=(-1)^{\frac {n-1}{2}}}" loading="lazy"></li>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {1}{n}}\right)=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/07b2a3eef03e7519a37bc536daf9abd9e5dd86a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:9.913ex; height:6.176ex;" alt="{\displaystyle \left({\frac {1}{n}}\right)=1}" loading="lazy"></li>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {a\;\mathrm {mod} \;n}{n}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f8ff063a0451cd9cb65d7f9fd02c641faaa847fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:20.668ex; height:6.176ex;" alt="{\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {a\;\mathrm {mod} \;n}{n}}\right)}" loading="lazy"></li></ul>

Die oben stehende Regel folgt aus der Definition des Jacobi-Symbol über den <a href="Charakter_(Mathematik)" title="Charakter (Mathematik)">Charakter</a>. Der Zähler des Jacobi-Symbols ist nur ein Repräsentant der Gruppe <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a+n\mathbb {Z} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a+n\mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e0e92568e19d6efe77e3f1b84241faaeae38214a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.015ex; height:2.343ex;" alt="{\displaystyle a+n\mathbb {Z} }" loading="lazy">; daher spielt es keine Rolle, welchen Repräsentanten man wählt.

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\cdot \left({\frac {b}{n}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/173034e3672db0b303bbf415711d8e4eee254ae0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:21.921ex; height:6.176ex;" alt="{\displaystyle \left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\cdot \left({\frac {b}{n}}\right)}" loading="lazy"> (Multiplikativität im Zähler)</li>

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\cdot \left({\frac {a}{n}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/09246ba2ce52a07eaf675249a2edeaa9b62212f2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:22.483ex; height:4.843ex;" alt="{\displaystyle \left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\cdot \left({\frac {a}{n}}\right)}" loading="lazy"> (Multiplikativität im Nenner)</li></ul>

Als Beispiel soll <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J(127,703)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J(127,703)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5a38792f6decab58c08a48dbdf63f6b180487152.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.289ex; height:2.843ex;" alt="{\displaystyle J(127,703)}" loading="lazy"> bestimmt werden:

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</msup>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {127}{703}}\right)=(-1)^{{\frac {126}{2}}{\frac {702}{2}}}\left({\frac {703}{127}}\right)=-\left({\frac {703}{127}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4888ce2354553658bf509787e82c183d4b868f0a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:42.702ex; height:6.176ex;" alt="{\displaystyle \left({\frac {127}{703}}\right)=(-1)^{{\frac {126}{2}}{\frac {702}{2}}}\left({\frac {703}{127}}\right)=-\left({\frac {703}{127}}\right)}" loading="lazy"></dd></dl>

Da man den Repräsentanten im Zähler frei wählen darf, ist dies gleich

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</msup>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -\left({\frac {68}{127}}\right)=-\left({\frac {2}{127}}\right)^{2}\cdot \left({\frac {17}{127}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bc76aa57537adcc4788889700b9d10853e34b9f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:33.069ex; height:6.509ex;" alt="{\displaystyle -\left({\frac {68}{127}}\right)=-\left({\frac {2}{127}}\right)^{2}\cdot \left({\frac {17}{127}}\right)}" loading="lazy"></dd></dl>

Da 2 zu 127 <a href="Teilerfremd" class="mw-redirect" title="Teilerfremd">teilerfremd</a> ist, ist J(2, 127) sicher nicht 0 und damit J(2, 127)2 = 1. Also fällt dieser Faktor weg und man erhält:

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</msup>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -\left({\frac {17}{127}}\right)=-(-1)^{{\frac {126}{2}}{\frac {16}{2}}}\left({\frac {127}{17}}\right)=-\left({\frac {127}{17}}\right)=-\left({\frac {8}{17}}\right)=-\left({\frac {2}{17}}\right)^{3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/76492fe5ce73ffb0113cffcd2621b0851323d31f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:70.457ex; height:6.509ex;" alt="{\displaystyle -\left({\frac {17}{127}}\right)=-(-1)^{{\frac {126}{2}}{\frac {16}{2}}}\left({\frac {127}{17}}\right)=-\left({\frac {127}{17}}\right)=-\left({\frac {8}{17}}\right)=-\left({\frac {2}{17}}\right)^{3}}" loading="lazy"></dd></dl>

Für die 2 im Zähler gibt es eine geschlossene Formel, daher erhält man schließlich:

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

<mrow>

<mrow>

<msup>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {127}{703}}\right)=-\left((-1)^{\frac {17^{2}-1}{8}}\right)^{3}=-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8a3e6af0c7ff49cc96325c2ae0c59206b4241e98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:32.885ex; height:6.843ex;" alt="{\displaystyle \left({\frac {127}{703}}\right)=-\left((-1)^{\frac {17^{2}-1}{8}}\right)^{3}=-1}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Algorithmus_–_Berechnung_des_Jacobi-Symbols_(a/b)">Algorithmus – Berechnung des Jacobi-Symbols (a/b)</h2></div>

<td>1

</td>

<td colspan="8">Eingabe <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\gets a,\,y\gets b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\gets a,\,y\gets b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5c3263288d3a518cecc53f5d26edd895121090d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.362ex; height:2.509ex;" alt="{\displaystyle x\gets a,\,y\gets b}" loading="lazy">

</td></tr>

<tr>

<td>2

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J\gets 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7e105a79eadfc4b562522f0772ba986d09866625.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.248ex; height:2.176ex;" alt="{\displaystyle J\gets 1}" loading="lazy">

</td></tr>

<tr>

<td>3

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/10f53b404b1fdd041a589f1f2425e45a2edba110.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.416ex; height:2.509ex;" alt="{\displaystyle y=1}" loading="lazy"> then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\gets 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\gets 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7b5d321bd29f00e00aed26e6b05bd977ab14fb50.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.106ex; height:2.176ex;" alt="{\displaystyle x\gets 1}" loading="lazy">

</td></tr>

<tr>

<td>4

</td>

<td colspan="8">while <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\neq 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\neq 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b9958361c7255c54e0e839727cf67a0f8ada2324.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.591ex; height:2.676ex;" alt="{\displaystyle x\neq 1}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J\neq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J\neq 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5169f942bbd1ed0d3ec892596895f7437da3d9e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.732ex; height:2.676ex;" alt="{\displaystyle J\neq 0}" loading="lazy"> do

</td></tr>

<tr>

<td>5

</td>

<td>

</td>

<td colspan="7">Berechne <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q\in \mathbb {Z} ,\,r\in \mathbb {N} _{0},{\text{ wobei }}x=q\cdot y+r{\text{ und }}0\leq r<y}">

</mrow>

<msub>

</mrow>

</mrow>

</msub>

<mtext> wobei </mtext>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q\in \mathbb {Z} ,\,r\in \mathbb {N} _{0},{\text{ wobei }}x=q\cdot y+r{\text{ und }}0\leq r<y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8c734c31b5d1ad035536b2c421325c743d614b60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:48.334ex; height:2.509ex;" alt="{\displaystyle q\in \mathbb {Z} ,\,r\in \mathbb {N} _{0},{\text{ wobei }}x=q\cdot y+r{\text{ und }}0\leq r<y}" loading="lazy">

</td></tr>

<tr>

<td>6

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/894a83e863728b4ee2e12f3a999a09f5f2bf1c89.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.31ex; height:2.176ex;" alt="{\displaystyle r=0}" loading="lazy"> then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J\gets 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J\gets 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/717dbc6202f8add61a6113749eb548bf03bf0f1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.248ex; height:2.176ex;" alt="{\displaystyle J\gets 0}" loading="lazy">

</td></tr>

<tr>

<td>7

</td>

<td>

</td>

<td colspan="7">else

</td></tr>

<tr>

<td>8

</td>

<td>

</td>

<td>

</td>

<td colspan="6">Berechne <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k,x'\in \mathbb {N} _{0},{\text{ wobei }}r=2^{k}\cdot x'{\text{ und }}x'{\text{ ungerade}}}">

<msup>

</msup>

<msub>

</mrow>

</mrow>

</msub>

<mtext> wobei </mtext>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</msup>

</mrow>

<msup>

</msup>

<mtext> ungerade</mtext>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k,x'\in \mathbb {N} _{0},{\text{ wobei }}r=2^{k}\cdot x'{\text{ und }}x'{\text{ ungerade}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4d16a147d62c394bb44f66185030abf709b292c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:44.745ex; height:3.009ex;" alt="{\displaystyle k,x'\in \mathbb {N} _{0},{\text{ wobei }}r=2^{k}\cdot x'{\text{ und }}x'{\text{ ungerade}}}" loading="lazy">

</td></tr>

<tr>

<td>9

</td>

<td>

</td>

<td>

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\equiv 1{\text{ mod }}2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cf4fb8be29dc0eb35a4099bada21611c52528009.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:12.187ex; height:2.176ex;" alt="{\displaystyle k\equiv 1{\text{ mod }}2}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\equiv \pm 3{\text{ mod }}8}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\equiv \pm 3{\text{ mod }}8}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/77e9acc00c85d98083cf3d79ce831ac98926e29f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.939ex; height:2.509ex;" alt="{\displaystyle y\equiv \pm 3{\text{ mod }}8}" loading="lazy"> then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J\gets -J}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J\gets -J}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7f6c20976ee7ac8362d37578a617072a9e6c1f7f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.365ex; height:2.343ex;" alt="{\displaystyle J\gets -J}" loading="lazy">

</td></tr>

<tr>

<td>10

</td>

<td>

</td>

<td>

</td>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/538bdb4c4940b4ded5c7f64a8cd8fb8174d21f9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.275ex; height:2.509ex;" alt="{\displaystyle x'=1}" loading="lazy"> then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\gets 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\gets 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7b5d321bd29f00e00aed26e6b05bd977ab14fb50.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.106ex; height:2.176ex;" alt="{\displaystyle x\gets 1}" loading="lazy">

</td></tr>

<tr>

<td>11

</td>

<td>

</td>

<td>

</td>

<td colspan="6">else

</td></tr>

<tr>

<td>12

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<mfrac>

<mrow>

<msup>

</msup>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {x'-1}{2}}\cdot {\frac {y-1}{2}}\equiv 1{\text{ mod }}2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4a246b127879549124f90973df9fb42a67d8bbe5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:25.502ex; height:5.509ex;" alt="{\displaystyle {\frac {x'-1}{2}}\cdot {\frac {y-1}{2}}\equiv 1{\text{ mod }}2}" loading="lazy"> then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J\gets -J}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J\gets -J}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7f6c20976ee7ac8362d37578a617072a9e6c1f7f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.365ex; height:2.343ex;" alt="{\displaystyle J\gets -J}" loading="lazy">

</td></tr>

<tr>

<td>13

</td>

<td>

</td>

<td>

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\gets y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/449eb0edbfa1dcdc2bbd0f93f93d469a45018036.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.099ex; height:2.176ex;" alt="{\displaystyle x\gets y}" loading="lazy">

</td></tr>

<tr>

<td>14

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\gets x'}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4f55d24727e8fd2bc3bdde23d74a4f600c980b8e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.784ex; height:2.843ex;" alt="{\displaystyle y\gets x'}" loading="lazy">

</td></tr>

<tr>

<td>15

</td>

<td colspan="8">Ausgabe <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/359e4f407b49910e02c27c2f52e87a36cd74c053.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.471ex; height:2.176ex;" alt="{\displaystyle J}" loading="lazy">

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Armin Leutbecher: Zahlentheorie. Springer-Verlag, 1996, ISBN 3-540-58791-8.</li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-09-15" href="https://de.wikipedia.org/wiki/?title=Jacobi-Symbol&oldid=259766540">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>